package me.timlong;

public class CountBackN {

    /**
     * 题目描述
     * 输入一个链表，输出该链表中倒数第k个结点。
     *
     *
     */
    public ListNode FindKthToTail(ListNode head,int k) {


        if(head == null && k == 0)
            return  null;

        ListNode former = head;
        ListNode later = former;

        while(k-- > 0   ){
            if(later == null)
                return null;
            later = later.next;
        }

        while(null != later){
            later = later.next;
            former = former.next;
        }
        return former;
    }


    /**
     * 题目描述
     * 输入一个链表，反转链表后，输出新链表的表头。
     * @param
     */
    public ListNode ReverseList(ListNode head) {
        if(head == null)
            return null;

        ListNode p = head;
        ListNode q = p.next;
        ListNode r = null;
        while(null != q){
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }
        head.next = null;
        return p;
    }

    /**
     题目描述
     输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
     *
     */

    public ListNode Merge(ListNode list1,ListNode list2) {
        if(null == list1)
            return list1;
        else if(null == list2)
            return list1;

        ListNode newls;
        if(list2.val < list1.val){
            newls = list2;
            list2 = list2.next;
        } else{
            newls = list1;
            list1 = list1.next;
        }
        ListNode newLsPoint = newls;

        while(null != list1 && null != list2){
            if(list2.val < list1.val){
                newLsPoint.next = list2;
                list2 = list2.next;
            } else {
                newLsPoint.next = list1;
                list1 = list1.next;
            }
            newLsPoint = newLsPoint.next;
        }
        if(null == list1)
            newLsPoint.next = list2;
        else
            newLsPoint.next = list1;


        return newls;
    }


    public static void main(String[] args) {

        ListNode ln1 = new ListNode(1);
        ListNode ln2 = new ListNode(2);
        ListNode ln3 = new ListNode(3);
        ListNode ln4 = new ListNode(4);
        ListNode ln5 = new ListNode(5);
        ListNode ln6 = new ListNode(6);

        ln1.next = ln2;
        ln2.next = ln3;
        ln3.next = ln4;
        ln4.next = ln5;
        ln5.next = ln6;


        ListNode ln1_2 = new ListNode(1);
        ListNode ln2_2 = new ListNode(3);
        ListNode ln3_2 = new ListNode(5);
        ListNode ln4_2 = new ListNode(7);
        ListNode ln5_2 = new ListNode(8);
        ListNode ln6_2 = new ListNode(10);

        ln1_2.next = ln2_2;
        ln2_2.next = ln3_2;
        ln3_2.next = ln4_2;
        ln4_2.next = ln5_2;
        ln5_2.next = ln6_2;

        ListNode currs = ln1_2;
        System.out.println("after: ");
        while(null != currs){
            System.out.println(currs.val);
            currs = currs.next;
        }

        System.out.println("********");



        ListNode newLs = new CountBackN().Merge(ln1, ln1_2);

        ListNode curr = newLs;
        System.out.println("after: ");
        while(null != curr){
            System.out.println(curr.val);
            curr = curr.next;
        }

    }
}